#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#define MAX_KEYS 20

typedef int ElementType;
typedef struct TREENODE TreeNode;
typedef TreeNode* Item;
typedef struct QUEUENODE QueueNode;


struct QUEUENODE {
	Item elm;
	QueueNode *next;
	QueueNode *top;
};

struct TREENODE {
	ElementType elm;
	TreeNode *left;
	TreeNode *right;
	int lh;
	int rh;
	int bf;
};

QueueNode *initQueue(void);
void inQueue(QueueNode*,Item);
_Bool queueEmpty(QueueNode*);
Item outQueue(QueueNode*);
TreeNode* insertNode(TreeNode*,ElementType);
int calcHigh(TreeNode*);
void preOrder(TreeNode*);
TreeNode* finderPos(TreeNode*,int);
void reBalance(TreeNode *founder,ElementType elm);

int main(void){
	int n;
	scanf("%d",&n);
	TreeNode *root=NULL;
	for(int i=0;i<n;i++){
		ElementType a;
		scanf("%d",&a);
		root=insertNode(root,a);
		calcHigh(root);

		//printf("\n");
		//preOrder(root);
		TreeNode *target;
		target=finderPos(root,i+1);
		if(NULL==target){}
			//printf("No Found\n");
		else{ //	rebalance
			//printf("Found\n");
			//printf("T:%d\n",target->elm);
			reBalance(target,a);
			calcHigh(root);
			//preOrder(root);
		}
	}
	printf("%d",root->elm);
	return 0;
}

void preOrder(TreeNode *root){
	if( NULL==root )
		return;
	//printf("V:%d BF:%d\n",root->elm,root->bf);
	preOrder(root->left);
	preOrder(root->right);
	return;
}

TreeNode* insertNode(TreeNode *root,ElementType elm){
	TreeNode *ret=root;
	TreeNode **head=&ret;
	while( root ){
		if( elm > (root->elm) ){
			head=&(root->right);
			root=root->right;
		}else{
			head=&(root->left);
			root=root->left;
		}
	}
	TreeNode *new=malloc(sizeof(TreeNode));
	new->elm=elm;
	new->left=new->right=NULL;
	new->lh=new->rh=new->bf=0;
	*head=new;
	return ret;
}

int calcHigh(TreeNode *root){
	if( NULL == root )
		return 0;
	root->lh=calcHigh(root->left)+1;
	root->rh=calcHigh(root->right)+1;
	root->bf=root->lh - root->rh;
	return root->lh > root->rh ? root->lh : root->rh ;
}
QueueNode *initQueue(void){
	QueueNode *ret=malloc(sizeof(QueueNode));
	ret->next=ret->top=NULL;
	return ret;
}
void inQueue(QueueNode *root,Item elm){
	QueueNode *new=malloc(sizeof(QueueNode));
	new->next=NULL;
	new->elm=elm;
	if( root->top ){
		root->top->next=new;
		root->top=new;
	}else{
		root->next=new;
		root->top=new;
	}
	return;
}

_Bool queueEmpty(QueueNode *root){
	if( root->next )
		return false;
	return true;
}

Item outQueue(QueueNode *root){
	Item ret=root->next->elm;
	QueueNode *t=root->next;
	root->next=root->next->next;
	free(t);
	if(!(root->next))
		root->top=NULL;
	return ret;
}

TreeNode* finderPos(TreeNode *root,int len){
	if(!root)
		return NULL;
	QueueNode *q=initQueue();
	Item treeNodeArr[MAX_KEYS];
	Item tmp;
	int i=0;
	inQueue(q,root);
	while( !queueEmpty(q) ){
		tmp=outQueue(q);
		treeNodeArr[i++]=tmp;
		if( tmp->left ){
			inQueue(q,tmp->left);
		}
		if( tmp->right ){
			inQueue(q,tmp->right);
		}
	}
	TreeNode *target=NULL;
	for(int i=0;i<len;i++){
		if( abs(treeNodeArr[i]->bf) > 1 )
			target=treeNodeArr[i];
	}
	if( NULL == target )
		return NULL;
	else
		return target;
}

void reBalance(TreeNode *founder,ElementType elm){
	if( elm < founder->elm ){
		if( elm < founder->left->elm ){		// ll
//printf("LL\n");
			ElementType founder_elm=founder->elm;
			founder->elm=founder->left->elm;
			TreeNode *new=malloc(sizeof(TreeNode));
			new->elm=founder_elm;
			new->left=founder->left->right;
			new->right=founder->right;
			founder->right=new;
			new=founder->left->left;
			free(founder->left);
			founder->left=new;
		}else{								//	lr
//printf("LR\n");
			ElementType founder_elm=founder->elm;
			founder->elm=founder->left->right->elm;
			TreeNode *new=malloc(sizeof(TreeNode));
			new->elm=founder_elm;
			new->left=founder->left->right->right;
			new->right=founder->right;
			founder->right=new;
			new=founder->left->right;
			founder->left->right=founder->left->right->left;
			free(new);
		}
	}else{
		if( elm < founder->right->elm ){		// rl
//printf("RL\n");
			ElementType founder_elm=founder->elm;
			founder->elm=founder->right->left->elm;
			TreeNode *new=malloc(sizeof(TreeNode));
			new->elm=founder_elm;
			new->left=founder->left;
			new->right=founder->right->left->left;
			founder->left=new;
			new=founder->right->left;
			founder->right->left=founder->right->left->right;
			free(new);
		}else{								// rr
//printf("RR\n");
			ElementType founder_elm=founder->elm;
			founder->elm=founder->right->elm;
			TreeNode *new=malloc(sizeof(TreeNode));
			new->elm=founder_elm;
			new->left=founder->left;
			new->right=founder->right->left;
			founder->left=new;
			new=founder->right;
			founder->right=founder->right->right;
			free(new);
		}
	}
}
